Implementations of SONET/SDH circuit-switchcd cross-connect switching structures may be designed to be non-blocking by providing sufficient hardware resources. (SONET is the North American equivalent of the SDH transmission standard; a reference here to SDH is intended to be a reference to either SDH or SONET.) For example, a three-stage Clos-type switching structure is made non-blocking by providing at least a certain minimum number of middle stage switches. The cost of a switch is proportional to the number of middle stage switches.
Reducing the number of middle switches in the architecture increases the blocking probability. However, if a new connection is initially blocked, it may sometimes be completed by rearranging existing connections. A rearrangement is not allowed to interrupt existing connections. A factor that makes rearranging connections difficult in an SDH signal environment is the multirate and multicast nature of SDH signals.
The 155,520 kbit/s Synchronous Transport Module-1 (STM-1) is the basic building block in an SDH network. An STM-1 signal consists of overhead and payload bytes organized in a 125 microsecond frame structure. The information is conditioned for serial transmission on the selected media (e.g. optical fiber) at a rate synchronized to the network. At each network node where the signal is demultiplexed, information is processed byte-by-byte.
The STM-1 signal uses a so-called Virtual Container (VC)--an information structure defined by the International Telecommunications Union (ITU)--to serve various Plesiochronous Digital Hierarchy (PDH) data rates. There are several different-capacity virtual containers: a VC-4 signal can transport 139,264 kbit/s; a VC-3 signal can transport either 44,736 kbit/s or 34,368 kbit/s; a VC-2 signal can transport 6,312 kbit/s; and a VC-12 signal can transport 2,048 kbit/s. An STM-1 signal may contain various combinations of different virtual containers, such as a single VC-4, or three VC-3s, or two VC-3s and seven VC-2s. It is perhaps fruitful to liken virtual containers to Russian nesting dolls, to imagine that in an STM-1 signal, lower-capacity virtual containers may be "nested" in larger-capacity virtual containers.
Existing SDH Digital Cross-Connect Systems (DCSs) are usually non-blocking or nearly non-blocking, made so by using complex hardware. One kind of architecture often used for such a DCS is a three-stage Clos-type network, made up of three interconnected switching stages: an input stage, middle stage, and output stage.
In a general SDH network environment, a cross-connect switching system makes connections that differ in three categories.
Unicast or multicast. A unicast connection supports traffic between two endpoints, while a multicast connection supports traffic from one endpoint to a group of endpoints. PA1 Unidirectional or bidirectional. In a unidirectional connection, data flows in only one direction: from a source to one or more destinations. In a bidirectional connection, both endpoints serve as both sources and destinations. Multicast connections can only be unidirectional. Bidirectional unicast traffic appears at a switch as two connections, one for each direction. PA1 Protected or not protected. In SubNetwork Connection Protection (SNCP), unicast data is sent simultaneously on two disjoint paths. If one of the paths degrades or fails, the data may still be correctly received on the other path. For generality, the point at which the connection splits into two streams or joins back into a single stream can occur within the network and is not restricted to the endpoints. Thus, the connection consists of concatenated segments of single streams and disjoint paths. SNCP connections appear at the switch in one of two forms. If the switch is at a split point, then it must support a connection from one input to two outputs. If the switch is at a merge point, then it must support a connection from two inputs to one output. Some further constraints exist regarding the timing relationship between the two streams, such as that the two streams must be synchronized to allow merging to occur properly.
Each stage in a three-stage SDH switching network may have either time, space, or both time and space switching capabilities. An SDH signal is basically time division multiplexing at a byte level. Repositioning virtual containers in the same STM-1 payload is time switching. Moving virtual containers from one STM-1 payload to another is space switching.
Several algorithms for rearranging Clos networks are known, e.g., a routing algorithm for rearranging three-stage Clos networks for single-rate unicast traffic. The most relevant existing algorithm for rearranging Clos networks is Paull's change algorithm. See M. C. Paull, Reswitching of Connection Networks, Bell Syst. Tech. J., vol. 41, pp 833-855, May 1962. In Paull's change algorithm, when the input requested is in input switch I, and the output requested is in output switch O, the algorithm searches for a middle switch m available for the connection request. Sometimes the link from input switch I to middle switch m, and the link from output switch O to middle switch m are free at the same time. Then no rearrangements of existing connections are required.
If there is no middle switch m found, then a rearrangement is necessary. The rearrangement procedure uses two middle switches, A and B, where A is one of the middle switches that is free (unused) from input switch I to a middle stage, but is not free from output switch O to the same middle stage. B is one of the middle switches that is free from output switch O to the middle stage but is not free from input switch I to the middle stage. Freeing up bandwidth through middle switch A or B is possible by swapping some existing connections using middle switch A or B.
The existing procedures work only for single-rate unicast traffic, and do not work with multirate SDH switching. It is not possible to directly modify or extend Paull's change algorithm or any other known algorithm to work with SDH switching. SNCP, a new ITU standardized capability, cannot be implemented inside of existing switching procedures. The SDH multirate signal hierarchy in combination with multicast requirements forecasted in SDH networks do not allow existing procedures to be used. Hardware costs motivate a move toward more complexity in the switching procedure. Desired connection capabilities of SDH unicast unidirectional, unicast bidirectional, unicast unidirectional SNCP, unicast bidirectional SNCP, and multicast render existing procedures highly inefficient or non-functional.